package com.github.yangyishe.p200;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 149. 直线上最多的点数
 * https://leetcode.cn/problems/max-points-on-a-line/description/?envType=study-plan-v2&envId=top-interview-150
 * todo 已解决, 但效率低
 *
 * 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：points = [[1,1],[2,2],[3,3]]
 * 输出：3
 * 示例 2：
 *
 *
 * 输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
 * 输出：4
 *
 *
 * 提示：
 *
 * 1 <= points.length <= 300
 * points[i].length == 2
 * -104 <= xi, yi <= 104
 * points 中的所有点 互不相同
 */
public class Problem149 {
    public static void main(String[] args) {
        int[][] points=new int[][]{
                {1,1},
                {3,2},
                {5,3},
                {4,1},
                {2,3},
                {1,4}
        };

        Problem149 problem149 = new Problem149();
        int maxPoints = problem149.maxPoints(points);
        System.out.println("maxPoints = " + maxPoints);

    }

    /**
     * 思路:
     * 判断3个以上的点是否在同一条直线上, 需要满足: (y3-y2)/(x3-x2)=(y2-y1)/(x2-x1), 或者x1=x2=x3
     *
     * 暴力算法, 对每两个点之间的斜率进行计算, 对每种斜率都放入一个map中, 最后计算size最多的斜率及其size. 如果斜率是无限, 可取Integer.MAX_VALUE.
     * 算法复杂度. O(n^2)
     * 小优化: 如果a&b与b&c构成了相同的直线, 则a&c也必然会构成相同的直线.
     *
     * 斜率相等后, 判定是否是相同的起始点. 即y=kx+c
     *
     *
     * @param points
     * @return
     */
    public int maxPoints(int[][] points) {
        if(points.length==1){
            return 1;
        }
        // 1. 构建临时节点
        Point[] pointsTemp=new Point[points.length];
        for(int i=0;i<points.length;i++){
            pointsTemp[i]=new Point(points[i][0],points[i][1]);
        }

        //2. 对每一个point按照斜率进行group化
        Map<String, Set<String>> rate2CountMap=new HashMap<>();
        for(int i=0;i<pointsTemp.length-1;i++){
            for(int j=i+1;j<pointsTemp.length;j++){
                Line line = pointsTemp[i].calcLine(pointsTemp[j]);
                rate2CountMap.putIfAbsent(line.toString(), new HashSet<>());
                Set<String> set =rate2CountMap.get(line.toString());
                        set.add(pointsTemp[i].toString());
                set.add(pointsTemp[j].toString());
            }
        }

        //3. 计数获得
        int maxCount=0;
        for (Set<String> pointSet : rate2CountMap.values()) {
            maxCount=Math.max(maxCount,pointSet.size());
        }

        return maxCount;
    }

    class Point{
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Line calcLine(Point another){
            if(another.x==this.x){
                return new Line(Integer.MAX_VALUE,this.x) ;
            }
            double rate=((double)(this.y- another.y))/(this.x- another.x);
            double orginY = this.y - this.x * rate;
            return new Line(rate,orginY);
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }

    class Line{
        // 如果是一条竖线, 则记为Integer.MAX_VALUE
        double rate;
        // 如果是一条竖线, 则记为organX
        double orginY;

        public Line(double rate, double orginY) {
            this.rate = rate;
            this.orginY = orginY;
        }

        @Override
        public String toString() {
            return "line{" +
                    "rate=" + rate +
                    ", orginY=" + orginY +
                    '}';
        }
    }
}


